An important use for a computer system is the manipulation of data. This manipulation is sometimes of value in itself, such as organizing a mass of information into tables easily comprehensible by human beings. At other times, the data is manipulated as part of some task that the computer is performing, such as a linear programming optimization process.
The data stored in a computer's memory must be accessed by the computer's control and manipulation circuitry. Conventional memory is composed of multiple locations, each capable of storing information. Each of these locations is much like a post office box. To use the contents of a particular box, you must know its unique identifying number or address. Whenever the computer requires a piece of data, it must know in which location(s) of memory the required data resides. The computer then specifies the address(es) of the appropriate location(s) to the memory, which, in turn, furnishes the computer with the data present in those location(s). Thus, the memory serves as a passive repository of whatever information the computer wishes to place in it.
A computer performs useful tasks by executing programs that are written for it. These programs must have knowledge of the data to be accessed and manipulated as part of the task at hand. Artisans who write these programs have an organizational scheme of data in their minds, but they frequently find it inconvenient to assign unique names or numbers to each elementary piece of data associated with a program at hand. Instead, programmers often organize the data into groups called data structures, a few common ones of which are described below.
One common data structure is a stack. In a stack, items are placed on "top" of one another like trays in a cafeteria. When an item is to be read from the stack, it is always the one at the top of the stack that is read. Similarly, when an item is to be written, it is always "pushed" onto the top of the stack. Thus, the stack is a "last-in-first-out" (LIFO) data organization.
Another common data structure is a tree. A tree is much like a genealogical chart. In a tree, there is a single piece of data that forms the head. This piece of data is called the root. The root is the first parent, and each parent can have one or more "children" (each child being a piece of data itself), and these children have more children, and so forth. These structures are, of course, abstract entities imposed by the program upon the data, but they do have a semantic significance to the users.
Whenever a computer program operates on data organized as a stack, for example, it is forced to translate its view of the stack into the terms the memory can understand, that is, into the numbered locations, or addresses. To successfully implement a stack, the processor must be able to remember where the current top of the stack is. The address of the top of the stack is stored, in turn, in another memory location. So to read the top item in a stack, the computer must first obtain the address which identifies the top of the stack. Once that address has been located, then the actual datum at that address must be requested. Operations such as adding an item to the top of the stack, deleting an item, etc., require analogous multiple memory accesses. In fact, even more accesses might be required since a careful program ought also to check whether the stack is within the location bounds allotted to it, or whether it is approaching a point where it may manipulate a location currently allotted to a different data structure. Clearly, there is a difference between the way memory is treated as a repository for data, and the way memory locations are doled out to programs.
A programmer typically expends considerable effort keeping track of the actual memory locations involved in each data structure. This book-keeping is not only cumbersome and error-prone, it is terribly inefficient. A simple task, such as a stack access, ideally would take but a single memory access. The burden of bounds checking and storage management causes this simple task to require many more accesses to memory.